package arithmetic;

import arithmetic2.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author: Jie
 * @Date: 2019/1/25 13:46
 * @Function :102. 二叉树的层次遍历
 * 难点，如何计算每层末尾。
 *
 * 1、BFS 复杂度 O n  ，一行一行写入。
 * 2、DFS 复杂度O n  ， 竖着插入每行，
 * 参考：
 * A_09_BinaryTree.java
 */
public class A_14_TreeBFS {
    public static void main(String[] args) {
        TreeNode treeRootNode = A_09_BinaryTree.getTreeRootNode();
        List<List<Integer>> mList = new ArrayList<>();
//        preOrderTraverse(treeRootNode,mList,0);
        bfs(treeRootNode,mList);
        for (List<Integer> zero : mList) {
            for (Integer nums:zero) {
                System.out.print(",");
                System.out.print(nums);
            }
            System.out.println("");
        }

    }

    //DFS 复杂度O n  ， 竖着插入每行，自行实现 ^_^
    /**
     *
     * @param root
     * @param mList
     * @param level  记录每行层数
     */
    public static void preOrderTraverse(TreeNode root, List<List<Integer>> mList, int level){
        if (root==null){
            return;
        }
        //根
        if (mList.size()>level) {
            List<Integer> integers = mList.get(level);
            integers.add(root.val);
        }else {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(root.val);
            mList.add(temp);
        }
        if (root.left!=null){
            preOrderTraverse(root.left,mList,level+1);
        }
        if (root.right!=null){
            preOrderTraverse(root.right,mList,level+1);
        }
    }

    //1ms 666
    public static void bfs(TreeNode root, List<List<Integer>> mList){
        if (root == null){
            return;
        }
        Queue<TreeNode> mQueue = new LinkedList<>();
        mQueue.offer(root);
//        visted = set (root); 图去重
        while (!mQueue.isEmpty()){
            int levelsize = mQueue.size();//每层大小
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelsize; i++) {
                TreeNode currentNode = mQueue.poll();
                currentLevel.add(currentNode.val);
                if (currentNode.left != null) {
                    mQueue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    mQueue.offer(currentNode.right);
                }
            }
            mList.add(currentLevel);
        }

    }
}
